package org.yumeko.mybatisplusdemo.utils;

import java.util.Arrays;

//
//用main方法写出过程并将结果打印到控制台，不能使用集合的排序函数及AI代码提示。
//将两个有序数组合并成一个有序数组，输入： [1,2,3,7,9]，[2,4,6]，输出： [1,2,2,3,4,6,7,9]
//1. 分治思想
//        将大问题分解为小问题
//分别处理后再合并结果
//2. 双指针技术
//使用两个指针（i 和 j）分别指向两个有序数组
//        通过比较指针所指元素的大小来决定处理顺序
//3. 归并过程
//        保持两个数组的有序性
//将两个有序数组合并成一个有序数组
//        算法复杂度
//时间复杂度: O(m + n) - 其中 m 和 n 分别是两个数组的长度
//空间复杂度: O(m + n) - 需要额外空间存储合并结果
//        应用场景
//归并排序 - 这是最主要的应用
//外部排序 - 处理大量数据时的排序算法
//链表排序 - 对链表进行排序的常用方法
//多路归并 - 合并多个有序数据流
//这是计算机科学中非常经典和重要的算法之一，特别适用于需要稳定排序和处理大量数据的场景
public class MergeOrderedArrays {
    public static int[] merge(int[] nums1, int[] nums2) {
        // 获取第一个数组的长度
        int m = nums1.length;
        // 获取第二个数组的长度
        int n = nums2.length;
        System.out.println("nums1: " + m);
        System.out.println("nums2: " + n);
        // 创建一个新的数组用于存储合并后的结果，长度为两个数组长度之和
        int[] result = new int[m + n];
        System.out.println("result: " + result.length);
        // 初始化三个指针：i指向nums1，j指向nums2，k指向result数组
        int i = 0, j = 0, k = 0;

        // 比较两个数组的元素，将较小的元素放入结果数组
        // 当两个数组都还有元素未处理时继续循环
        while (i < m && j < n) {
            // 如果nums1当前元素小于等于nums2当前元素
            if (nums1[i] <= nums2[j]) {
                // 将nums1的当前元素放入结果数组，并将i和k指针后移
                result[k++] = nums1[i++];
            } else {
                // 将nums2的当前元素放入结果数组，并将j和k指针后移
                result[k++] = nums2[j++];
            }
        }

        // 将nums1中剩余的元素复制到结果数组
        // 如果nums1还有剩余元素
        while (i < m) {
            result[k++] = nums1[i++];
        }

        // 将nums2中剩余的元素复制到结果数组
        // 如果nums2还有剩余元素
        while (j < n) {
            result[k++] = nums2[j++];
        }

        // 返回合并后的有序数组
        return result;
    }
    public static void main(String[] args) {
        // 测试用例
        int[] nums1 = {1, 2, 3, 7, 9};
        int[] nums2 = {2, 4, 6};

        // 合并两个有序数组
        int[] merged = merge(nums1, nums2);

        // 打印结果
        System.out.print(Arrays.toString(merged));
    }
}
